/// @file rootedtree.cc
/// @brief Methods for the rooted tree classes

// *************************************************************************

// Copyright© 2010 Texas A&M University, 
//                 College Station, Texas
//                 Contact: R Crosby <rwc@cs.tamu.edu>
//
// Copyright© 2003, 2004 by BiRC -- Bioinformatics Research Center
//                 University of Aarhus, Denmark
//                 Contact: Thomas Mailund <mailund@birc.dk>
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

// *************************************************************************

#include <list>
#include <stack>
#include <cassert>
#include <algorithm>

#include "rootedtree.hh"
#include "S.hh"
#include "unrootedtree.hh"

class BuildRootedTreeVisitor : public UnrootedTreeVisitor {
private:
    bool firstLeaf;
    RootedTree *_tree;
    std::stack<UnrootedTreeNode *> _previous;
    std::stack<RootedTreeNode *> _parents;
public:
    BuildRootedTreeVisitor(RootedTree *tree) { firstLeaf = true; _tree = tree; }
    virtual ~BuildRootedTreeVisitor() {}
    void visit_leaf(UnrootedTreeLeaf *leaf);
    void visit_inner(UnrootedTreeInner *inner);
};

void
BuildRootedTreeVisitor::visit_leaf ( UnrootedTreeLeaf *leaf )
{

    if(firstLeaf){

	firstLeaf = false;
	RootedTreeRoot *root = new RootedTreeRoot(leaf->s());

	//update tree
	_tree->_root = root;
	_tree->_nodes.push_back(root);

	//update stacks
	_parents.push(root);
	_previous.push(leaf);

	//recurse
	leaf->neighbour()->accept(this);

	//update stacks
	_parents.pop();
	_previous.pop();

    }

    else {

	RootedTreeLeaf* rleaf = new RootedTreeLeaf(leaf->s());
	rleaf->parent(_parents.top());
	_parents.top()->add_child(rleaf);

	//update tree
	_tree->_nodes.push_back(rleaf);
	_tree->_leafs.push_back(rleaf);

    }

}

void
BuildRootedTreeVisitor::visit_inner(UnrootedTreeInner *inner)
{

    RootedTreeInner *rinner = new RootedTreeInner();
    rinner->parent(_parents.top());
    _parents.top()->add_child(rinner);

    //update tree
    _tree->_nodes.push_back(rinner);

    //update stacks
    //recurse
    for(int i = 0; i < 3; ++i) {

	if(inner->neighbours()[i] != _previous.top()) {

	    _parents.push(rinner);
	    _previous.push(inner);
	    inner->neighbours()[i]->accept(this);
	    _previous.pop();
	    _parents.pop();

	}

    }

}

void
RootedTreeRoot::accept(RootedTreeVisitor *visitor,
		       const char *       fn,
		       const unsigned     ln )
{
    visitor->visit_root( this, fn, ln );
}

void
RootedTreeLeaf::accept(RootedTreeVisitor *visitor)
{
    visitor->visit_leaf(this);
}

void
RootedTreeInner::accept(RootedTreeVisitor *visitor)
{
    visitor->visit_inner(this);
}

void
RootedTreeRoot::add_child(RootedTreeNode *child) 
{
    //dont add a child twice
    assert(_child == 0);
    _child = child;
}

void
RootedTreeInner::add_child(RootedTreeNode *child)
{
    //dont add more than two children
    assert((_left == 0) || (_right == 0));
    if(_left == 0) 
    {
	_left = child;
    }
    else 
    {
	_right = child;
    }
}

void
RootedTreeLeaf::add_child(RootedTreeNode *child) {
    //shouldn't get here (but anyways the method really shouldn't be
    //here - design flaw)
    assert(0);
}


namespace {

    class has_label : public std::unary_function<UnrootedTreeLeaf*,bool> {
	const std::string &_label;
    public:
	has_label(const std::string &label) : _label(label) {}
	bool operator() (UnrootedTreeLeaf *n) const {
	    return n->s()->Name() == _label;
	}
    };

}

// *****************************************************************************

RootedTree::RootedTree ( UnrootedTree*  ut, 
			 string         s )
{
    list<UnrootedTreeLeaf *>::iterator root_itr;
    root_itr = find_if(ut->leafs().begin(),ut->leafs().end(),has_label(s));
    assert(root_itr != ut->leafs().end());
    UnrootedTreeLeaf *u_root = *root_itr;
    BuildRootedTreeVisitor rtv(this);		  // Guarantee it's destroyed
    u_root->accept(&rtv);
}

// *****************************************************************************

RootedTree::~RootedTree() 
{

    while ( !_nodes.empty() ) {
	delete _nodes.back();
	_nodes.pop_back();
    }

}
